{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 1. Search" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*I have moved to the top of the page all of the imports that I will need for this notebook.*" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import matplotlib.pyplot as plt\n", "import random\n", "import math\n", "import copy\n", "\n", "%matplotlib inline" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1.1 The TSP" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For these examples, I need a hard problem. How about the Traveling Salesperson Problem (TSP)? The problem is: given a set of cities, what is the shortest path that will visit all of them, and return home?\n", "\n", "First we need a set of cities. I use a dictionary to associate each number of a city with its geographical location:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "cities = {0: (60, 200), 1: (180, 200), 2: (80, 180), 3: (140, 180),\n", " 4: (20, 160), 5: (100, 160), 6: (200, 160), 7: (140, 140),\n", " 8: (40, 120), 9: (100, 120), 10: (180, 100), 11: (60, 80),\n", " 12: (120, 80), 13: (180, 60), 14: (20, 40), 15: (100, 40),\n", " 16: (200, 40), 17: (20, 20), 18: (60, 20), 19: (160, 20)}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's see where these cities are:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def distance(a, b):\n", " return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def plot_tour(tour):\n", " plt.figure(figsize=(6, 6))\n", " xy = [cities[i] for i in tour] + [cities[tour[0]]]\n", " axes = plt.gca()\n", " axes.set_xlim([0, 200])\n", " axes.set_ylim([0, 200])\n", " plt.plot([d[0] for d in xy], [d[1] for d in xy], \"-o\")\n", " \n", "def scatter_tour(tour):\n", " plt.figure(figsize=(6, 6))\n", " xy = [cities[i] for i in tour] + [cities[tour[0]]]\n", " axes = plt.gca()\n", " axes.set_xlim([0, 200])\n", " axes.set_ylim([0, 200])\n", " plt.scatter([d[0] for d in xy], [d[1] for d in xy])\n", " \n", "def tour_distance(tour):\n", " total = 0\n", " current = tour[0]\n", " for city in tour[1:]:\n", " total += distance(cities[current], cities[city])\n", " current = city\n", " total += distance(cities[tour[-1]], cities[tour[0]])\n", " return total" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "tour_distance(range(20))" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "scatter_tour(range(20))" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "plot_tour(range(20))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "How hard is this problem? It turns out that TSP is as hard as they come. We call this **NP hard**. It is very hard because there are so many possibilities, and each new city multiplies those possibilities. And, the problem can't be divided into subproblems (like sorting can be).\n", "\n", "For an $n$ city problem, there are factorial($n - 1$) possible routes. Consider just 20 cities." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# Iterative solution:\n", "def factorial(n):\n", " retval = 1\n", " for i in range(1, n + 1):\n", " retval = retval * i\n", " return retval\n", "\n", "# Recursive solution:\n", "def factorial(n):\n", " if n == 1:\n", " return 1\n", " else:\n", " return n * factorial(n - 1)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "factorial(20 - 1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To know if we found the shortest, we might have to check all of those. But that is far too many. This kind of problem is often called intractable.\n", "\n", "$$ O(factorial(n - 1)) $$\n", "\n", "$$ O(n!) $$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1.2 Greedy Method" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "How can we solve this problem of searching for the optimal path? As an example, suppose that you could just pick the closest city to visit at each city. This is called a \"greedy\" method, because it greedily picks the locally closest.\n", "\n", "How good is it?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def greedy_method():\n", " tour = [0]\n", " while True:\n", " min_dist = 100000\n", " min_city = -1\n", " for j in range(20):\n", " if j in tour or tour[-1] == j:\n", " continue\n", " dist = distance(cities[tour[-1]], cities[j])\n", " if dist < min_dist:\n", " min_dist = dist\n", " min_city = j\n", " if min_city == -1:\n", " break\n", " tour.append(min_city)\n", " return tour" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "%%time\n", "greedy_tour = greedy_method()\n", "greedy_tour" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "tour_distance(greedy_tour)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "plot_tour(greedy_tour)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Not too bad, but we can do better. Ok, let's try some other algorithms." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1.3 Guess and Step" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's consider a simple method of problem solving: **guess and step**. First, just make a guess and note how close you are to a solution. Next, pick some piece of your guess and consider a slight change. If the variation is worse, don't make the change. If the variation is better, go ahead make the change. Now, continue making slight changes until you get a good enough solution. We will need:\n", "\n", "* a method of representing a problem (e.g., **dna**, or **tour**)\n", "* a measure of how good the guess is (e.g., a **fitness score**)\n", "* a method of making slight changes (e.g., **mutation**)\n", "\n", "At this point it is clear to see that analogy with Biological systems.\n", "\n", "Let's explore an iterative guess-and-check algorithm.\n", "\n", "We need a method for creating random \"tours\":" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def make_tour():\n", " ret_list = []\n", " for i in range(len(cities)):\n", " city = random.choice(range(len(cities)))\n", " while city in ret_list:\n", " city = random.choice(range(len(cities)))\n", " ret_list.append(city)\n", " return ret_list" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "guess = make_tour()\n", "guess" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "tour_distance(guess)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "plot_tour(guess)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "And we need a method for measure a tour's \"fitness\". We'll use \"total distance\"." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "format": "row" }, "outputs": [], "source": [ "def fitness(tour):\n", " return tour_distance(tour)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "fitness(greedy_tour)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "fitness(guess)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Finally, we need a method of mutating a tour. Tours aren't just random numbers: they are a circuit. For this problem, we'll use a specialized mutation function that just swaps two cities. That way it will always be a valid circuit." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def mutate(tour):\n", " tour = copy.copy(tour)\n", " # Pick two points and swap:\n", " point1 = random.randint(0, len(cities) - 1)\n", " point2 = random.randint(0, len(cities) - 1)\n", " tour[point1], tour[point2] = tour[point2], tour[point1]\n", " return tour" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "print(guess)\n", "guess = mutate(guess)\n", "print(guess)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now, let's iteratively mutate the guess, and ignore it if it is worse, but replace the original guess if the mutation is better." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "guess = make_tour()\n", "fit_list = [fitness(guess)]\n", "\n", "for i in range(10000):\n", " new_guess = copy.copy(guess)\n", " for j in range(2):\n", " new_guess = mutate(new_guess)\n", " f1 = fitness(guess)\n", " f2 = fitness(new_guess)\n", " if f2 < f1:\n", " fit_list.append(f2)\n", " guess = new_guess\n", " else:\n", " fit_list.append(f1)\n", "plt.plot(fit_list, marker=\"o\")\n", "plt.figure()\n", "plot_tour(guess)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "guess, fitness(guess)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "That's not too bad! Perhaps a bit better than the greedy method used. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1.4 Hill Climbing" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This guess-and-step methodology is actually called *hill climbing* due to the following metaphor. Start at a random place on a hill. Pick a direction to step. If the place you would step to is higher than where you are, make the step, otherwise stay where you are. This little algorithm will eventually take you to the top of the hill. However, it might might not take you to the highest place around because you could get trapped on a little plateau (i.e., you would have to step to a lower place before stepping to even higher ground).\n", "\n", "This is part of Computer Science that can be viewed as \"search for the solution.\"\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def hillclimb(times):\n", " guess = make_tour()\n", " fit_list = [fitness(guess)]\n", "\n", " for i in range(times):\n", " new_guess = mutate(guess)\n", " f1 = fitness(guess)\n", " f2 = fitness(new_guess)\n", " if f2 < f1:\n", " fit_list.append(f2)\n", " guess = new_guess\n", " else:\n", " fit_list.append(f1)\n", " plt.plot(fit_list, marker=\"o\")\n", " plt.figure()\n", " plot_tour(guess)\n", " return guess, fitness(guess)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "hillclimb(10000)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "fit_list[-1]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1.5 Random Search" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "One solution to getting stuck on a plateau is to make random moves. If you do that all of the time, that is called \"random search\"." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def random_search(times):\n", " guess = make_tour()\n", " fit_list = [fitness(guess)]\n", "\n", " for i in range(times):\n", " new_guess = mutate(guess)\n", " f1 = fitness(guess)\n", " f2 = fitness(new_guess)\n", " if random.random() > .5:\n", " fit_list.append(f2)\n", " guess = new_guess\n", " else:\n", " fit_list.append(f1)\n", " plt.plot(fit_list, marker=\"o\")\n", " plt.figure()\n", " plot_tour(guess)\n", " return guess, fitness(guess)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "random_search(1000)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1.6 Simulated Annealing" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A slightly better version of hill climbing allows you to take random steps sometimes, regardless of whether or not the step would put you on higher ground. Of course, you don't always want to take random steps (that's called *random search*), so you'll need to control your randomness. If you only take random steps as dictated by a schedule, then you are using *simulated annealing*. Simulated annealing allows you to start off taking random steps quite often, but then slowly curb the habit. This works better than hill climbing when the ground is fairly smooth.\n", "\n", "" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def simulated_annealing(times):\n", " guess = make_tour()\n", " fit_list = [fitness(guess)]\n", "\n", " for i in range(times):\n", " new_guess = mutate(guess)\n", " f1 = fitness(guess)\n", " f2 = fitness(new_guess)\n", " if random.random() > i/times:\n", " # Pick random:\n", " if random.random() < .5:\n", " fit_list.append(f1) \n", " else:\n", " fit_list.append(f2)\n", " guess = new_guess\n", " elif f2 < f1:\n", " fit_list.append(f2)\n", " guess = new_guess\n", " else:\n", " fit_list.append(f1)\n", " plt.plot(fit_list, marker=\"o\")\n", " plt.figure()\n", " plot_tour(guess)\n", " return guess, fitness(guess)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "simulated_annealing(100000)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1.7 Can we do better?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Simulated annealing can be described as a **\"balance between Exploitation and Exploration\".**\n", "\n", "What could be better than simulated annealing? How about a whole group of people spread over the country side, each as their own simulated annealer? And they can communicate with each other. \"Hey, I'm on high ground over here!\" or \"This area looks promising! Come over here!\" This is the idea behind evolutionary algorithms." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1.8 Evolutionary Algorithms" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Evolutionary algorithms are techniques for searching through a solution landscape in a generally effective manner. \n", "\n", "All evolutionary strategies have a core set of properties:\n", "\n", "* A \"population\" of solutions\n", "* Limited resources (not all solutions will survive)\n", "* A measure of performance, called ''fitness''\n", "* Preferential treatment toward the higher measured solutions (the most fit ones)\n", "* Reliance on randomness\n", "\n", "A typical evolutionary system follows this basic algorithm:\n", "\n", "1. Create a random population of solutions\n", "2. Compute a fitness measure for each\n", "3. Create new members by mutating and/or combining old ones\n", "4. Select the most fit for the next generation\n", "5. Go to Step #3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.8.1 Mutation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Mutation is the act of changing one gene in a genome. Often simulated mutation can take two forms: incremental mutation, or random value mutation. Incremental mutation takes the value of the gene and changes it by +/- a small amount. Random value mutation replaces the value by a random value between min and max." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.8.2 Crossover" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Crossover exchanges pieces of two genomes. Crossover can be a perfect shuffle, uniform, or point-based. Shuffle simply alternates between each parent. Uniform tosses an even coin to see if the gene comes from the mother or the father. Point-based mutation will only crossover at particular points. Shown here is a single point crossover:\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.8.3 Selection" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Those genes with the higher fitness are more likely to survive to the next generation.\n", "\n", "In many implementations, crossover and selection are combined such that parents give rise to children that replace the lower fitness genomes." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.8.4 Variations" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "There are two main flavors of evolutionary systems: the genetic algorithm (GA), and genetic programming (GP). GAs use a fixed genome size composed of bits, or, more generally, floating point numbers. GP uses trees of programming language expressions that can grow and shrink. If using a GA, then the human encoder of the problem assigns a meaning for each number in the gene. In a GP, the human encoder must create the functions and terminals used in the expressions, but the system builds its own representations. We will examine both of these techniques in the following sections." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1.9 Genetic Algorithm" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To get started, we need three things:\n", "\n", "1. a fitness function (fitness should always be >= 0)\n", "2. a function to determine when we should stop\n", "3. a random population" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "format": "tab" }, "outputs": [], "source": [ "target = \"METHINKS IT IS LIKE A WEASEL\"\n", "\n", "\"Hidden Target phrase\"" ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "collapsed": false }, "outputs": [], "source": [ "import string" ] }, { "cell_type": "code", "execution_count": 34, "metadata": { "collapsed": true }, "outputs": [], "source": [ "alphabet = string.ascii_uppercase + \" \"" ] }, { "cell_type": "code", "execution_count": 35, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def make_guess():\n", " return [random.choice(alphabet) for c in range(len(target))]\n", "\n", "def make_pop(size):\n", " pop = []\n", " for i in range(len(target)):\n", " pop.append([0, make_guess()])\n", " return pop\n", "\n", "def mutate(guess):\n", " guess = copy.copy(guess)\n", " point = random.randint(0, len(target) - 1)\n", " guess[point] = random.choice(alphabet)\n", " return guess\n", " \n", "def fitness(guess):\n", " return sum([guess[i] == target[i] for i in range(len(target))])\n", "\n", "def select(pop):\n", " index = 0\n", " partsum = 0.0\n", " sumFitness = sum([item[0] for item in pop])\n", " if sumFitness == 0:\n", " raise Exception(\"Population has a total of zero fitness\")\n", " spin = random.random() * sumFitness\n", " while index < len(pop) - 1:\n", " fitness = pop[index][0]\n", " if fitness < 0:\n", " raise Exception(\"Negative fitness in select: \" + str(fitness))\n", " partsum += fitness\n", " if partsum >= spin:\n", " break\n", " index += 1\n", " return copy.copy(pop[index][1])\n", "\n", "def crossover(pop):\n", " for j in range(int(len(pop)/2)):\n", " p1 = select(pop)\n", " p2 = select(pop)\n", " point = random.randint(0, len(target) - 1)\n", " child = []\n", " for i in range(len(target)):\n", " if i < point:\n", " child.append(p1[i])\n", " else:\n", " child.append(p2[i])\n", " pop[len(pop) - j - 1][1] = child" ] }, { "cell_type": "code", "execution_count": 36, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "'IOWILEUOXQTHHKOZRECTUNXXADGF'" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "guess = make_guess()\n", "\"\".join(guess)" ] }, { "cell_type": "code", "execution_count": 37, "metadata": { "collapsed": true }, "outputs": [], "source": [ "pop = make_pop(10)" ] }, { "cell_type": "code", "execution_count": 38, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[0,\n", " ['X',\n", " 'X',\n", " 'W',\n", " 'L',\n", " 'R',\n", " 'Q',\n", " 'O',\n", " 'L',\n", " 'H',\n", " 'Z',\n", " 'U',\n", " 'U',\n", " 'T',\n", " 'N',\n", " 'V',\n", " 'P',\n", " 'D',\n", " 'G',\n", " 'U',\n", " 'A',\n", " 'E',\n", " 'V',\n", " 'P',\n", " 'G',\n", " 'D',\n", " 'Q',\n", " 'K',\n", " 'S']]" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pop[0]" ] }, { "cell_type": "code", "execution_count": 39, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "['N', 'U', 'A', 'J', 'A', 'V', 'B', 'L', 'T', 'G', 'Z', 'S', ' ', 'N', 'O', 'O', 'Y', 'L', 'G', 'K', 'I', 'L', 'T', 'I', 'G', 'R', ' ', 'O']\n", "['N', 'U', 'A', 'J', 'A', 'V', 'B', 'L', 'T', 'G', 'Z', 'S', ' ', 'N', 'O', 'O', 'Y', 'L', 'G', 'K', 'I', 'L', 'T', 'I', 'K', 'R', ' ', 'O']\n" ] } ], "source": [ "guess = make_guess()\n", "print(guess)\n", "print(mutate(guess))" ] }, { "cell_type": "code", "execution_count": 40, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "0" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "fitness(pop[0][1])" ] }, { "cell_type": "code", "execution_count": 41, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def evolve(pop):\n", " generations = 0\n", " while True:\n", " for i in range(len(pop)):\n", " pop[i][0] = fitness(pop[i][1])\n", " pop.sort(reverse=True)\n", " if pop[0][0] == len(target):\n", " break\n", " for i in range(2, 10): # not the top 20%\n", " pop[i][1] = mutate(pop[i][1])\n", " crossover(pop)\n", " if generations % 10 == 0:\n", " print(\"generations:\", generations, \"fitness:\", pop[0][0], \"\".join(pop[0][1]))\n", " generations += 1\n", " print(\"generations:\", generations, \"fitness:\", pop[0][0], \"\".join(pop[0][1]))" ] }, { "cell_type": "code", "execution_count": 42, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "generations: 0 fitness: 4 MPNXZOWZRPHLCS QXNONTQOAYLQL\n", "generations: 10 fitness: 7 MLWMIFPV ZTNCH QXASKCVUEOSXF\n", "generations: 20 fitness: 8 MLTMIQPV YTNCH QXASECVUEOSXF\n", "generations: 30 fitness: 9 MLTMITKM YTWCH BXA KHAUEOSXF\n", "generations: 40 fitness: 11 MQTMITKM YTNCH BXPEKHA ERSEF\n", "generations: 50 fitness: 12 MSTMITKM YTNCH BMPE IATEESEF\n", "generations: 60 fitness: 14 MQTHITKM YT CH BMPE IATEESEF\n", "generations: 70 fitness: 15 MTTHITKM YT CH BXPE NATELSEL\n", "generations: 80 fitness: 17 MTTHIWKM YT MH BXKE SATEASEL\n", "generations: 90 fitness: 17 MZTHIWKM YT MH BXKE ATEASEL\n", "generations: 100 fitness: 18 MTTHIXKM YT KH BIKE SNTEASEL\n", "generations: 110 fitness: 19 MZTHIYKM YT MH BIKE FJWEASEL\n", "generations: 120 fitness: 20 MZTHIYKM YT MH BIKE AAWEASEL\n", "generations: 130 fitness: 20 MZTHIYKT YT MH BIKE AAWEASEL\n", "generations: 140 fitness: 20 MZTHIYKT YT MQ XIKE AAWEASEL\n", "generations: 150 fitness: 20 MZTHTNKT YT MQ XIKE AJWEASEL\n", "generations: 160 fitness: 20 MZTHTNKT YT MQ XIKE AJWEASEL\n", "generations: 170 fitness: 20 MZTHXNKY RT PQ CIKE ATWEASEL\n", "generations: 180 fitness: 21 METHXNKY RT GQ IIKE ACWEASEL\n", "generations: 190 fitness: 21 METHXNKY RT GQ IIKE ACWEASEL\n", "generations: 200 fitness: 21 METHXNKY RT GQ IIKE ACWEASEL\n", "generations: 210 fitness: 22 METHXNK RT RS BIKE ACWEASEL\n", "generations: 220 fitness: 22 METHXNKI RT RS BIKE ACWEASEL\n", "generations: 230 fitness: 23 METHXNKI RT IS RIKE ACWEASEL\n", "generations: 240 fitness: 23 METHXNKI ZT IS WIKE AIWEASEL\n", "generations: 250 fitness: 23 METHXNKQ ZT IS WIKE ASWEASEL\n", "generations: 260 fitness: 24 METHINKI ZT IS WIKE ASWEASEL\n", "generations: 270 fitness: 25 METHINKV IT IS WIKE ASWEASEL\n", "generations: 280 fitness: 25 METHINKV IT IS WIKE AXWEASEL\n", "generations: 290 fitness: 26 METHINKS IT IS WIKE AXWEASEL\n", "generations: 300 fitness: 26 METHINKS IT IS WIKE AYWEASEL\n", "generations: 310 fitness: 26 METHINKS IT IS XIKE AXWEASEL\n", "generations: 320 fitness: 26 METHINKS IT IS XIKE AYWEASEL\n", "generations: 330 fitness: 26 METHINKS IT IS XIKE AYWEASEL\n", "generations: 340 fitness: 26 METHINKS IT IS XIKE AYWEASEL\n", "generations: 350 fitness: 26 METHINKS IT IS XIKE AYWEASEL\n", "generations: 360 fitness: 26 METHINKS IT IS XIKE AYWEASEL\n", "generations: 370 fitness: 26 METHINKS IT IS XIKE AYWEASEL\n", "generations: 380 fitness: 26 METHINKS IT IS XIKE AYWEASEL\n", "generations: 390 fitness: 26 METHINKS IT IS XIKE AYWEASEL\n", "generations: 400 fitness: 26 METHINKS IT ISLLIKE AHWEASEL\n", "generations: 410 fitness: 26 METHINKS IT ISLLIKE ASWEASEL\n", "generations: 420 fitness: 26 METHWNKS IT ISLLIKE A WEASEL\n", "generations: 430 fitness: 27 METHINKS IT ISLLIKE A WEASEL\n", "generations: 440 fitness: 27 METHINKS IT ISLLIKE A WEASEL\n", "generations: 450 fitness: 27 METHINKS IT ISLLIKE A WEASEL\n", "generations: 460 fitness: 27 METHINKS IT ISLLIKE A WEASEL\n", "generations: 470 fitness: 27 METHINKS IT ISOLIKE A WEASEL\n", "generations: 480 fitness: 27 METHINKS IT ISOLIKE A WEASEL\n", "generations: 490 fitness: 27 METHINKS IT ISOLIKE A WEASEL\n", "generations: 500 fitness: 27 METHINKS IT ISOLIKE A WEASEL\n", "generations: 510 fitness: 27 METHINKS IT ISOLIKE A WEASEL\n", "generations: 520 fitness: 27 METHINKS IT ISOLIKE A WEASEL\n", "generations: 530 fitness: 27 METHINKS IT ISOLIKE A WEASEL\n", "generations: 540 fitness: 27 METHINKS IT ISOLIKE A WEASEL\n", "generations: 550 fitness: 27 METHINKS IT ISOLIKE A WEASEL\n", "generations: 560 fitness: 27 METHINKS IT ISYLIKE A WEASEL\n", "generations: 570 fitness: 27 METHINKS IT ISYLIKE A WEASEL\n", "generations: 576 fitness: 28 METHINKS IT IS LIKE A WEASEL\n" ] } ], "source": [ "pop = make_pop(10)\n", "evolve(pop)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 2. Further Reading" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "1. Holland, John H. (1975) *Adaptation in Natural and Artificial Systems*. The University of Michigan Press, Ann Arbour." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.5.2" } }, "nbformat": 4, "nbformat_minor": 0 }